

		POMUL DE CRACIUN - SOLUTIE
	       ----------------------------

	Urmatoarele 2 observatii sunt esentiale pt. orice algoritm ce rezolva problema data:
1) Pt. orice i,j = 1,2,..,n, actionarea succesiva a becurilor i si j este echivalenta cu actionarea
succesiva a becurilor j si i; drept urmare in orice solutie putem considera ca numerele becurilor
actionate apar in ordine crescatoare;
2) Actionarea de 2 ori a aceluiasa bec are efect nul; drept urmare in orice solutie putem consi-
dera ca fiecare bec apare cel mult o data.

	In concluzie o submultime a multimii {1,2,..,n}. Mai mult, putem cere ca numerele becurilor
sa apara in ordine strict crescatoare.
	Simplificarile mentionate, fara alte rafinari ulterioare, fac insa ca determinarea unei so-
lutii sa necesite timp exponential, inacceptabil pt. valori mari ale lui n.



	Elevul Virgil Palanciuc, care a obtinut punctajul maxim, a prezentat un algoritm recursiv
ce urmareste determinarea unei solutii in care becurile actionate apar in ordinea crescatoare a
numerelor lor de ordine. Esenta algoritmului este constituita de functia booleana "try", avand
drept argument numarul unui bec; este intoarsa valoarea TRUE daca exista o succesiune (crescatoare)
de actionari care aprinde toate becurile. Un apel try(x) are loc doar daca prin actionarea lui x
se aprinde un bec stins (evident acesta este chiar x sau un vecin al sau). In lantul de apelari
succesive, numerele de ordine ale argumentelor cresc, asigurandu-se astfel si forma anuntata a
solutiei, dar in acelasi timp evitandu-se ciclarea. Efectul functiei este urmatorul:

1) actioneaza becul x, schimband starea si vecinilor sai;
2) daca toate becurile sunt aprinse, este scrisa valoarea lui x si apelul se incheie prin intoar-
cerea valorii TRUE; in caz contrar treci la 3);
3) se alege un bec stins u oarecare (nu conteaza care anume, deoarece oricum trebuie aprinse toate
becurile). Se apeleaza succesiv try(u'), pt. u'=x si u' vecin al lui u, dar numai daca u'>x. Pt.
prima din aceste apelari care intoarce valoarea TRUE, este scrisa valoarea lui x si apelul try(x)
se incheie prin intoarcerea valorii TRUE; daca nici una din incercari nu poate ajunge la situatia
in care toate becurile sa fie aprinse, se trece la 4);
4) se schimba starea lui x si a vecinilor sai, revenindu-se in configuratia cu care s-a inceput
apelul.
	Programul principal seteaza toate becurile ca fiind stinse si inscrie pe fiecare linie i
a matricei A vecinii lui i, inclusiv el insusi (A[i,0] memoreaza valoarea 1+nr. vecinilor lui i,
A[i,1]=i, iar pe urmatoarele A[i,0]-1 pozitii apar vecinii lui i). Apoi pt. i=1,2,..,n se ape-
leaza try(i), cautandu-se deci o succesiune crescatoare de actionari care incepe cu actionarea
lui i; imediat ce un astfel de apel intoarce TRUE, programul se termina (se cere o solutie oare-
care).


	Cea mai completa este solutia propusa de Radu Lupsa, elaborata insa dupa terminarea con-
cursului. Solutia, prezentata in continuare, are 2 atuuri decisive; complexitatea in timp de or-
dinul O(n) si faptul ca demonstreaza existenta solutiei pt. orice arbore.
	Oricarui arbore ii atasam 3 atribute notate prin A,B,C. Spunem ca un arbore:
1) are atributul A daca exista o metoda de aprindere a tuturor varfurilor in care radacina este
actionata
2) are atributul B daca exista o metoda de aprindere a tuturor varfurilor in care radacina nu este
actionata;
3) are atributul C daca exista o metoda de aprindere a tuturor varfurilor cu exceptia radacini,
metoda in care radacina nu este actionata.

PROPOZITIE: Orice arbore are cel putin 2 dintre atributele A,B,C.
-----------	
	Sa observam ca afirmatia din enunt contine faptul ca este posibil ca toate varfurile sa
fie aprinse, deci demonstreaza existenta solutiei problemei propuse pt. orice arbore.
	Facem demonstratia prin inductie dupa numarul n de varfuri ale arborelui.
	Pt. n=1, este evident ca arborele format dintr-un singur varf are atributele A si C.
	Presupunem acum proprietatea adevarata pt. toti arborii avand cel mult n varfuri si consi-
deram un arbore cu n+1 varfuri. Fie r radacina sa, i1,..,ik descendentii lui r si I1,..,Ik subar-
borii de radacini i1,..,ik. Deosebim 2 cazuri:

1) Cel putin unul din subarborii I1,..,Ik are atributele A si B. Putem presupune, fara a restrange
generalitatea, ca I1 are atributele A si B. Atunci arborele are atributele B si C: conform ipote-
zei de inductie, varfurile subarborilor I2,..,Ik pot fi aprinse. In continuare, folosind unul din
atrinutele A sau B ale lui I1 putem aprinde toate varfurile acestui arbore si aprinde sau nu rada-
cina (de exemplu, daca verm sa aratam ca arborele are atributul C si in urma aprinderii tuturor
varfurilor subarborilor I1,..,Ik se obtine ca radacina este aprinsa, vom folosi atibutul B pt. I1).

2) Nici unul dintre subarborii I1,..,Ik nu are atat atributul A cat si atributul B. Drept urmare fi-
ecare din acesti arbori are fie atributele A si C, fie atributele B si C. Intregul arbore are atri-
butul A: folosim pt. toti subarborii atributul C si apoi actionam radacina. De asemenea intregul
arbore are atributele B sau C: folosim pt. toti subarborii atributul diferit de C pe care il are
si in functie de starea care rezulta pt. radacina vom obtine atributul B sau C pt. intregul arbore.

	Algoritmul are la baza considerentele din demonstratia propozitiei anterioare si consta
din 2 etape: determinarea tipurilor (radacinilor) subarborilor si precizarea unei modalitati de
aprindere a tutror varfurilor.

	Pt. determinarea tipurilor varfurilor (a se citi: subarborilor avand aceste varfuri drept
radacini) se apeleaza procedura recursiva TIPARB ce realizeaza o percurgere in postordine a arbo-
relui. Apelata pt. un varf r oarecare, ea calculeaza tipul acestuia astfel:

if r teminal then tipul este AC
else	if exista descendenti de tipul AB
	then tipul este BC
        else if numarul arborilor de tip AC este par then tipul este AC
	     else tipul este AB.

	Pt. a decide ce varfuri pot fi aprinse se parcurge arborele in preordine. In acest scop se
utilizeaza procedura Rez avand 2 argumente: varful curent r si atributul care trebuie folosit. Se
incepe prin a da variabilei j valoarea 0 sau 1 si atributul care trebuie folosit, dupa cum r are un
numar par sau impar de descendenti directie de tipul AC. Apoi:
- daca se aplica atributul A: se va aplica atributul C pt. toti fiii;
- daca se aplica atributul B sau C, atunci pt. fiecare fiu:
  - daca varful are atributul C, atunci se aplica celalalt atribut
  - daca varful are atributele A si B: se fol. A sau B in functie de ceilalti subarbori ai rada-
cinii; 	

(Mugurel Ionut Andreica):

nmin[x, 0] = nr minim de atingeri pt a aduce in starea finala subarborele lui x (inclusiv pe x) si x nu a fost atins
nmin[x, 1] = nr minim de atingeri pt a aduce in starea finala subarborele lui x (insclusiv x) si x este atins

nmin[x, j] se calculeaza pe baza valorilor fiiilor
